package ljl.codetop300;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class _349_intersection {

  /**
   * 求交集除了放到 set 里还有别的法吗
   * 它说每个元素大小不超过一千，那就搞个数组当 map 吧
   */
  static class test {

    public int[] intersection(int[] nums1, int[] nums2) {
      int[] dic1 = new int[1001];
      for (int i : nums1) {
        dic1[i] = 1;
      }
      List<Integer> same = new ArrayList<>();
      for (int i : nums2) {
        if (dic1[i] == 1) {
          same.add(i);
          dic1[i] = 2;
        }
      }
      return same.stream().mapToInt(Integer::valueOf).toArray();
    }
  }

  /**
   * 排序加双指针
   */
  static class off_sort {
    public int[] intersection(int[] nums1, int[] nums2) {
      Arrays.sort(nums1);
      Arrays.sort(nums2);
      int[] arr = new int[Math.max(nums1.length, nums2.length)];
      int i = 0, j = 0;
      int k = 0;
      while (i < nums1.length && j < nums2.length) {
        if (nums1[i] == nums2[j]) {
          if (k == 0 || arr[k - 1] != nums1[i]) arr[k++] = nums1[i];
          i++;
          j++;
        } else if (nums1[i] > nums2[j]) j++;
        else i++;
      }
      return Arrays.copyOfRange(arr, 0, k);
    }
  }
}
